{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Linked List Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeElements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移除链表元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你一个链表的头节点 <code>head</code> 和一个整数 <code>val</code> ，请你删除链表中所有满足 <code>Node.val == val</code> 的节点，并返回 <strong>新的头节点</strong> 。\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/06/removelinked-list.jpg\" style=\"width: 500px; height: 142px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,6,3,4,5,6], val = 6\n",
    "<strong>输出：</strong>[1,2,3,4,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [], val = 1\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [7,7,7,7], val = 7\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>列表中的节点数目在范围 <code>[0, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>1 <= Node.val <= 50</code></li>\n",
    "\t<li><code>0 <= val <= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-linked-list-elements](https://leetcode.cn/problems/remove-linked-list-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-linked-list-elements](https://leetcode.cn/problems/remove-linked-list-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,6,3,4,5,6]\\n6', '[]\\n1', '[7,7,7,7]\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        dummy_head = ListNode(0, head)\n",
    "        \n",
    "        \n",
    "        # 遍历列表并删除值为val的节点\n",
    "        saved = dummy_head\n",
    "        while dummy_head.next:\n",
    "            if dummy_head.next.val == val:\n",
    "                dummy_head.next = dummy_head.next.next\n",
    "            else:\n",
    "                dummy_head = dummy_head.next\n",
    "        \n",
    "        return saved.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head, val):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type val: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        a = []\n",
    "        while head:\n",
    "            a.append(head.val)\n",
    "            head = head.next\n",
    "        \n",
    "        for i in range(a.count(val)):\n",
    "            a.remove(val)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head, val):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type val: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        while head:\n",
    "            if head.val != val:\n",
    "                res.append(head.val)\n",
    "            head = head.next\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head, val):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type val: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        dm = ListNode(-1)\n",
    "        cur = dm\n",
    "        while head:\n",
    "            n = head\n",
    "            head = head.next\n",
    "            n.next = None\n",
    "            if n.val != val:\n",
    "                cur.next = n\n",
    "                cur = cur.next\n",
    "        return dm.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head, val):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type val: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        pre=ListNode(0)\n",
    "        pre.next=head\n",
    "        res=pre\n",
    "        \n",
    "        while head:\n",
    "            if head.val==val:\n",
    "                head=head.next\n",
    "                pre.next=head\n",
    "            else:\n",
    "                head=head.next\n",
    "                pre=pre.next\n",
    "        \n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        while head.val == val:\n",
    "            head = head.next\n",
    "            if not head:\n",
    "                return None\n",
    "        \n",
    "        q = head\n",
    "        p = q.next\n",
    "        while p:\n",
    "            if p.val == val:\n",
    "                q.next = p.next\n",
    "            else:\n",
    "                q = q.next\n",
    "            p = p.next\n",
    "\n",
    "        return head\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head, val):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type val: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        cur = dummy = ListNode(-1)\n",
    "        while head:\n",
    "            if head.val != val:\n",
    "                cur.next = head\n",
    "                cur = cur.next\n",
    "            head = head.next\n",
    "        cur.next = None\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head, val):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type val: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        re = ListNode(0)\n",
    "        n = re\n",
    "        while True:\n",
    "            if head:\n",
    "                v = head.val\n",
    "                nex = head.next\n",
    "                if v != val:\n",
    "                    temp = ListNode(v)\n",
    "                    n.next = temp\n",
    "                    n = temp\n",
    "                head = head.next\n",
    "            else:\n",
    "                break\n",
    "        return re.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head == None:\n",
    "            return head \n",
    "        s = head\n",
    "        pre = None\n",
    "        while s:\n",
    "            if s.val == val:\n",
    "                if pre == None:\n",
    "                    head =  s.next \n",
    "                else:\n",
    "                    pre.next = s.next \n",
    "                s = s.next\n",
    "            else:\n",
    "                pre = s\n",
    "                s = s.next\n",
    "        return head "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head == None: return head\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while cur and cur.next:\n",
    "            if cur.next.val == val:\n",
    "                pre = cur.next\n",
    "                while pre and pre.next and pre.next.val == val:\n",
    "                    pre = pre.next\n",
    "                cur.next = pre.next\n",
    "            cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        prehead=ListNode(-1)\n",
    "        prehead.next=head\n",
    "        precur,cur=prehead,head\n",
    "        \n",
    "        while cur:\n",
    "            if cur.val==val:\n",
    "                precur.next=cur.next\n",
    "                cur=cur.next\n",
    "            else:\n",
    "                precur=cur\n",
    "                cur=cur.next\n",
    "        return prehead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        pre = ListNode(0)\n",
    "        pre.next = head\n",
    "        tmp = pre\n",
    "        q = head\n",
    "        while q:\n",
    "            if q.val == val:\n",
    "                pre.next = q.next\n",
    "            else:\n",
    "                pre = q\n",
    "            q = q.next   \n",
    "        return tmp.next\n",
    "\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.next = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\r\n",
    "        dummy = ListNode(-1, head)\r\n",
    "        pre = dummy\r\n",
    "        cur = head\r\n",
    "        while cur:\r\n",
    "            if cur.val == val:\r\n",
    "                pre.next = cur.next\r\n",
    "            else:\r\n",
    "                pre = pre.next\r\n",
    "            cur = cur.next\r\n",
    "        return dummy.next\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        # 两个指针，一前一后\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        pre, cur = dummy, head\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "                cur = pre.next\n",
    "            else:\n",
    "                pre = pre.next\n",
    "                cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        head.prev = None\n",
    "        cur = head\n",
    "        while cur != None:\n",
    "            if cur.val == val and cur.prev:\n",
    "                cur.prev.next = cur.next\n",
    "                cur.next\n",
    "            elif cur.val == val and not cur.prev:\n",
    "                head = head.next\n",
    "                if head:\n",
    "                    head.prev = None\n",
    "                cur = head\n",
    "                continue\n",
    "            if cur.next:\n",
    "                if cur.val == val:\n",
    "                    cur.next.prev = cur.prev\n",
    "                else:\n",
    "                    cur.next.prev = cur\n",
    "            cur = cur.next\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        dummy_node = ListNode(next=head)\n",
    "        prev = dummy_node\n",
    "        # 双指针操作\n",
    "        while (head != None):\n",
    "            if head.val == val:\n",
    "                prev.next = head.next\n",
    "                head = head.next\n",
    "            else:\n",
    "                prev = head\n",
    "                head = head.next\n",
    "        \n",
    "        return dummy_node.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        while head and head.val == val:\n",
    "            head = head.next\n",
    "        \n",
    "        pre, cur = head, head\n",
    "        while cur:\n",
    "            if cur.val == val:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                pre = cur\n",
    "\n",
    "            cur = cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        dummy = ListNode\n",
    "        dummy.next = head\n",
    "        prev = dummy\n",
    "        while (head != None and prev.next != None):\n",
    "            if head.val == val:\n",
    "                prev.next = head.next\n",
    "                head = head.next\n",
    "            else:\n",
    "                prev = head\n",
    "                head = head.next\n",
    "        return dummy.next\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        dummy_head = ListNode(next=head) #添加一个虚拟节点\n",
    "        cur = dummy_head\n",
    "        while(cur.next!=None):\n",
    "            if(cur.next.val == val):\n",
    "                cur.next = cur.next.next #删除cur.next节点\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return dummy_head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        dummy_head = ListNode(next = head)  #创建虚拟头结点\n",
    "        cur = dummy_head\n",
    "        while cur.next:\n",
    "            if cur.next.val == val:\n",
    "                cur.next = cur.next.next\n",
    "            else:\n",
    "                cur = cur.next\n",
    "\n",
    "        return dummy_head.next #最终是返回创建的虚拟头结点的下一个元素，之所以不是head，是因为head有可能被我们删除\n",
    "        \n",
    "        # dummy_head = ListNode[next = head]\n",
    "        # current = dummy_head\n",
    "        # while current.next:\n",
    "        #     if current.val == val:\n",
    "        #         current.next = current.next.next\n",
    "        #     else:\n",
    "        #         current = current.next\n",
    "            \n",
    "        # return dummy_head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        dummy_head = ListNode(next=head)\n",
    "        cur = dummy_head\n",
    "        while(cur.next!=None):\n",
    "            if cur.next.val == val :\n",
    "                cur.next = cur.next.next\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return dummy_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next = head)\n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            if cur.next.val == val:\n",
    "                cur.next = cur.next.next\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        new_head = ListNode(head)\n",
    "        pre = new_head\n",
    "        pre.next = head\n",
    "        while pre and pre.next:\n",
    "            while pre.next and pre.next.val == val:\n",
    "                pre.next = pre.next.next\n",
    "            pre = pre.next\n",
    "        return ListNode(new_head.next.val, new_head.next.next) if new_head.next else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        root = ListNode(0)\n",
    "        root.next = head\n",
    "        pre, cur = root, head\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            if cur.val == val:\n",
    "                cur.next=None\n",
    "                pre.next=nxt\n",
    "                cur = nxt\n",
    "            else:\n",
    "                cur = nxt\n",
    "                pre = pre.next\n",
    "        return root.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def create_linklist_tail(li):\n",
    "    head=ListNode(li[0])\n",
    "    tail=head\n",
    "    for element in li[1:]:\n",
    "        node=ListNode(element)\n",
    "        tail.next=node\n",
    "        tail=node\n",
    "    return head\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head,val) :\n",
    "        if head==None:\n",
    "            return None\n",
    "        ln=[]\n",
    "        while head:\n",
    "            if head.val!=val:\n",
    "                ln.append(head.val)\n",
    "            head=head.next\n",
    "        if len(ln)==0:\n",
    "            return None\n",
    "        return create_linklist_tail(ln)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        #  可以直接删除链表中的节点，也可以使用 [] 记录val，然后生成链表\n",
    "        # stack = []\n",
    "        # while head:\n",
    "        #     stack.append(head.val)\n",
    "        #     head = head.next\n",
    "        # res = ans = ListNode(0)\n",
    "        # while stack:\n",
    "        #     a = stack.pop(0)\n",
    "        #     if a != val:\n",
    "        #         res.next = ListNode(a)\n",
    "        #         res = res.next\n",
    "        # return ans.next\n",
    "        ans = pre = ListNode(0)\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val != val:\n",
    "                pre.next = ListNode(cur.val)\n",
    "                pre = pre.next\n",
    "            cur = cur.next\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        first = ListNode(1)\n",
    "        head1 = first\n",
    "        second = head\n",
    "        while second != None:\n",
    "            if second.val == val:\n",
    "                second = second.next\n",
    "            else:\n",
    "                first.next = ListNode(second.val)\n",
    "                first = first.next\n",
    "                second = second.next\n",
    "        return head1.next\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        cur = ListNode()\n",
    "        cur.next = head\n",
    "        new_head = cur\n",
    "\n",
    "        while cur.next:\n",
    "            if cur.next.val == val:\n",
    "                temp = cur.next.next\n",
    "                del cur.next\n",
    "                cur.next = temp                \n",
    "            else:\n",
    "                cur = cur.next\n",
    "            \n",
    "        return new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def init(self, data):\n",
    "        if len(data) == 0:\n",
    "            return\n",
    "        self.head = ListNode(data[0])\n",
    "        p = self.head\n",
    "        for i in data[1:]:\n",
    "            node = ListNode(i)\n",
    "            p.next = node\n",
    "            p = p.next\n",
    "        return self.head\n",
    "\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head:\n",
    "            while head.val == val:\n",
    "                if not head.next:\n",
    "                    return\n",
    "                head = head.next\n",
    "            head.next = self.removeElements(head.next, val)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if not head or head==None:\n",
    "            return head\n",
    "        if head.val==val:\n",
    "            return self.removeElements(head.next,val)\n",
    "        p=head\n",
    "        while head.next!=None:\n",
    "            if head.next.val==val:\n",
    "                head.next=head.next.next\n",
    "            else:\n",
    "                head=head.next\n",
    "        return p\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "        \n",
    "        start_node = head\n",
    "        while start_node is not None and start_node.val == val:\n",
    "            start_node = start_node.next\n",
    "        \n",
    "        if start_node is None:\n",
    "            return None\n",
    "        start_node.next = self.removeElements(start_node.next, val)\n",
    "        return start_node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if not head:\n",
    "           return None\n",
    "        head.next = self.removeElements(head.next, val)\n",
    "        return head.next if head.val == val else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        \"\"\"\n",
    "        跟leetcode [83]类似，但这里是未排序的\n",
    "        \"\"\"\n",
    "        # 边界检测\n",
    "        if not head:\n",
    "            return \n",
    "        if head.val == val:\n",
    "            return self.removeElements(head.next, val)\n",
    "        if not head.next:\n",
    "            return head\n",
    "        \n",
    "        # 指针循环\n",
    "        p = head\n",
    "        p_next = head.next\n",
    "\n",
    "        while p_next: \n",
    "            if p_next.val == val:\n",
    "                # 如果查找到了，则只改动p的next指针指向，和移动p_next\n",
    "                p.next = p_next.next\n",
    "                p_next = p_next.next\n",
    "            else:\n",
    "                # 如果没找到，则p和p_next同时移动\n",
    "                p = p_next\n",
    "                p_next = p_next.next\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        while head and head.val == val:\n",
    "            head = head.next\n",
    "        if head:\n",
    "            head.next = self.removeElements(head.next, val)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        if head.val == val:\n",
    "            return self.removeElements(head.next, val)\n",
    "        node = head\n",
    "        while node.next:\n",
    "            if node.next.val == val:\n",
    "                node.next = node.next.next\n",
    "            else:\n",
    "                node = node.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if not head:\n",
    "            return head \n",
    "        if head and not head.next:\n",
    "            if head.val != val:\n",
    "                return head\n",
    "            else:\n",
    "                return head.next\n",
    "        if head.next.val == val:\n",
    "            head.next = head.next.next\n",
    "            self.removeElements(head,val)\n",
    "        else:\n",
    "            self.removeElements(head.next,val)\n",
    "        return head if head.val != val else head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "        if head.val == val:\n",
    "            head = head.next\n",
    "            head = self.removeElements(head,val)\n",
    "            return head\n",
    "        temp = head.next\n",
    "        pre = head\n",
    "        while(temp!=None):\n",
    "            if temp.val == val:\n",
    "                pre.next = temp.next\n",
    "            else:\n",
    "                pre = temp\n",
    "            temp = temp.next\n",
    "                \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "        head.next = self.removeElements(head.next, val)\n",
    "        return head.next if head.val == val else head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: ListNode, val: int) -> ListNode:\n",
    "        def remove(node:ListNode):\n",
    "            if not node or not node.next:\n",
    "                return\n",
    "            if node.next.val==val:\n",
    "                node.next=node.next.next\n",
    "                remove(node)\n",
    "            else:\n",
    "                remove(node.next)\n",
    "        while head and head.val==val:\n",
    "            head=head.next\n",
    "        if head:\n",
    "            remove(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return head\n",
    "        dummy=ListNode(0,head)\n",
    "        def digui(cur):\n",
    "            if not cur.next:\n",
    "                return \n",
    "            if cur.next.val==val:\n",
    "                cur.next=cur.next.next\n",
    "            else:\n",
    "                cur=cur.next\n",
    "            return digui(cur)\n",
    "        digui(dummy)\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        dummy=ListNode()\n",
    "        p=dummy\n",
    "        dummy.next=head\n",
    "        def removes(p):\n",
    "            #print(p)\n",
    "            if not p:\n",
    "                return\n",
    "            if p.next and p.next.next and p.next.val==val:\n",
    "                p.next=p.next.next\n",
    "            elif p.next and not p.next.next and p.next.val==val :\n",
    "                p.next=None\n",
    "            else:\n",
    "                p=p.next\n",
    "            return removes(p)\n",
    "        removes(p)\n",
    "        return dummy.next\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return None\n",
    "        if head.val == val:\n",
    "            return self.removeElements(head.next, val)\n",
    "        node = head\n",
    "        while node and node.next:\n",
    "            if node.next.val == val:\n",
    "                node.next = node.next.next\n",
    "            else:\n",
    "                node = node.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        dummy = ListNode(next = head)\n",
    "        cur = dummy\n",
    "        def backtracing(cur):\n",
    "            if not cur.next :\n",
    "                return\n",
    "            if cur.next.val == val:\n",
    "                cur.next = cur.next.next\n",
    "            else:\n",
    "                cur = cur.next\n",
    "            backtracing(cur)\n",
    "        backtracing(cur)\n",
    "        return cur.next\n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        if head == None:\n",
    "            return None\n",
    "        elif head.val == val:\n",
    "            return self.removeElements(head.next,val)\n",
    "        \n",
    "        p = head.next\n",
    "        q = head\n",
    "        while p :\n",
    "            if p.val == val:\n",
    "                q.next = p.next\n",
    "                p = p.next\n",
    "            else:\n",
    "                q = p\n",
    "                p = p.next\n",
    "        \n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        if head==None:\n",
    "            return head\n",
    "        else:\n",
    "            if head.val==val:\n",
    "                while head!=None and head.val==val:\n",
    "                    head=head.next\n",
    "                if head==None:\n",
    "                    return head\n",
    "            head.next=self.removeElements(head.next,val)\n",
    "            return head\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        # linked list is a recursively-defined DS\n",
    "        if not head:\n",
    "            return head\n",
    "        # remove val in the shorter linked list \n",
    "        res = self.removeElements(head.next, val)\n",
    "        if head.val == val:\n",
    "            # discard the head node\n",
    "            return res\n",
    "        # keep the head node, append the body already removed val\n",
    "        head.next = res\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                #print(f'not node')\n",
    "                return None\n",
    "            if node.val == val:\n",
    "                #print(f'node.val{node.val} == {val}')\n",
    "                return dfs(node.next)\n",
    "            else:\n",
    "                #print(f'node.next{node.val}')\n",
    "                node.next = dfs(node.next)\n",
    "            return node\n",
    "        return dfs(head)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
